package com.wellsfargo.bm;

public class BinarySearchTree {

	Node root;
	
	BinarySearchTree(){
		
	}
	BinarySearchTree(Node r){
		this.root=r;
	}
	
	BinarySearchTree(int[] A){
		root=buildBST(A,0,A.length-1);
	}
	
	public Node buildBST(int[] A, int l, int r){
		if(l>r)
			return null;
		int mid=l+(r-l)/2;
		Node node=new Node(A[mid]);
		node.left=buildBST(A,l,mid-1);
		node.right=buildBST(A,mid+1,r);
		if(node.left!=null)node.left.parent=node;
		if(node.right!=null)node.right.parent=node;
		return node;
	}
	
	public void inOrderTraversal(Node current){
		if(current==null)
			return;
		inOrderTraversal(current.left);
		System.out.println(current.value);
		inOrderTraversal(current.right);
	}
	
	public Node[] search(Node current, Node parent,int value){
		Node[] nodePair=new Node[2];
		nodePair[0]=null;
		nodePair[1]=current;
		if(current.value==value)
			return nodePair;
		nodePair[0]=current;
		if(current.value>value)
			search(current.left,current,value);
		else
			search(current.right,current,value);
		return nodePair;
	}
	
	public void insert(int value){
		Node[] nodePair=search(root,null,value);
		assert(nodePair[1]==null);
		Node newNode= new Node(value);
		newNode.parent=nodePair[0];
		if(nodePair[0].value>value)
			nodePair[0].left=newNode;
		else
			nodePair[0].right=newNode;
		
		Node current=newNode;
		while(current!=null){
			if(current.parent.left==current)
				current.parent.leftNodes++;
			else
				current.parent.rightNodes++;
		}
		
	}
	
	public NodePair getllfromBST1(Node node){
		NodePair p= getllfromBST(node);
		traverseLL(p.head);
		return p;
	}
	
	
	public NodePair getllfromBST(Node node){
		if(node==null || node.left==null && node.right==null)
			return new NodePair(node,node);
		
		NodePair left=getllfromBST(node.left);
		NodePair right=getllfromBST(node.right);
		
		if(node.left==null){
			node.right=right.head;
			right.head.left=node;
			return new NodePair(node,right.tail);
		}
		if(node.right==null){
			node.left=left.tail;
			left.tail.right=node;
			return new NodePair(left.head,node);
		}
		node.right=right.head;
		right.head.left=node;
		node.left=left.tail;
		left.tail.right=node;
		return new NodePair(left.head,right.tail);
	}
	
	public void traverseLL(Node node){
		while(node.right!=null){
			System.out.println(node.value);
			node=node.right;
		}
	}
	
}
